﻿using System.Linq;
using NUnit.Framework;
using ProjectEuler.Core.Helpers;

namespace ProjectEuler.Core
{
    public class Problem69 : IProjectEulerProblem
    {
        public int Number
        {
            get { return 69; }
        }

        public string Description
        {
            get { return "Find the value of n <= 1,000,000 for which n/φ(n) is a maximum."; }
        }

        public string Answer
        {
            get { return FindMaxNOverTotient(1000000).ToString(); }
        }

        protected int FindMaxNOverTotient(int nMax)
        {
            int max = 0;
            double maxTerm = 0.0;
            for (int n = 2; n <= nMax; n++)
            {
                var term = n*1.0/Totient(n);
                if (term > maxTerm)
                {
                    max = n;
                    maxTerm = term;
                }
            }
            return max;
        }

        // general formula for Euler's Totient Function
        protected int Totient(long n)
        {
            var primeFactorsOfN = MathHelper.PrimeFactorsOf(n).Distinct();
            double phiN = n;
            foreach (var primeFactorOfN in primeFactorsOfN)
            {
                phiN *= (1 - (1/(primeFactorOfN * 1.0)));
            }
            return (int)phiN;
        }
    }

    [TestFixture]
    public class Problem69Tests : Problem69
    {
        [Test]
        public void Can_get_Totient_function_results()
        {
            Assert.That(Totient(2), Is.EqualTo(1));
            Assert.That(Totient(3), Is.EqualTo(2));
            Assert.That(Totient(4), Is.EqualTo(2));
            Assert.That(Totient(5), Is.EqualTo(4));
            Assert.That(Totient(6), Is.EqualTo(2));
            Assert.That(Totient(7), Is.EqualTo(6));
            Assert.That(Totient(8), Is.EqualTo(4));
            Assert.That(Totient(9), Is.EqualTo(6));
            Assert.That(Totient(10), Is.EqualTo(4));
        }

        [Test]
        public void Check_that_n_of_6_produces_max_term()
        {
            Assert.That(FindMaxNOverTotient(10), Is.EqualTo(6));
        }

        [Test]
        public void Can_get_totient_of_1000000()
        {
            // this test information supplied by Wolfram Alpha to test upper bounds
            Assert.That(Totient(1000000), Is.EqualTo(400000));
        }
    }
}